import java.util.Random;

//数组中的第K个最大元素
//https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
public class Test {
    public static void main(String[] args) {
        //
    }
}


class Solution {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums,0,nums.length-1,k);
    }

    private int qsort(int[] nums, int l, int r,int k) {//[l,r]未排序的区间
        //
        int left  = l-1;
        int right = r+1;
        int i = l;
        int key = nums[new Random().nextInt(r-l+1)+l];//这里自己写的好像有点问题，好像阴差阳错对了
        while (i < right) {
            if (nums[i] < key) {
                swap(nums,i++,++left);
            }else if (nums[i] > key) {
                swap(nums,i,--right);
            }else{
                i++;
            }
        }
        //[l,left] [left+1,right-1] [right,r]
        int b = (right-1)-(left+1)+1;
        int c = r-right+1;

        if(c>=k){
            return qsort(nums,right,r,k);
        } else if ((b+c)>=k) {
            return key;//这里很巧妙
        }else{
            return qsort(nums,l,left,k-b-c);//这里参数的传递，尤其要注意“k”——k-b-c
        }
    }

    private void swap(int[] nums,int i,int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}




//我自己写的，通过了，但是感觉没有老师的清楚
class Solution1 {
    public int findKthLargest(int[] nums, int k) {
        int l = 0, r = nums.length - 1;
        int len = nums.length;
        qsort(nums,l,r,k);
        return nums[len-k+1];
    }

    private void qsort(int[] nums, int l, int r,int k) {//[l,r]表示还没有扫描判断的区间
        int left = l-1, right = r + 1;//left:小于key的最右边界，right：大于key的最左边界
        int a = 0,b = 0,c = 0;//分别表示三个区间的长度
        int i = left;
        int key = nums[new Random().nextInt(right - left + 1) + left];//随机指定一个key
        while (i < right) {
            if (nums[i] < key) {
                swap(nums,i++,++left);

            }else if(nums[i] == key){
                i++;

            }else{
                swap(nums,right--,i);
                c = r-right+1;
            }
        }

        a = left-l+1;
        b = (right-1)-(left+1)+1;
        c = r-right+1;
        if(c>=k){
            qsort(nums,right,r,k);
        }else if((b+c)>=k){
            return;
        }else{
            //对最左边实行查找
            qsort(nums,l,left,k-b-c);
        }

    }



    private void swap(int[] nums,int i,int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
